The invention regards a communication network with a plurality of network nodes, a method of routing data packets in such communication network and a method of locating and securing data of a desired resource in such communication network. More particularly, the invention regards a communication network and methods for efficient and effective distribution and discovery of recources in large-scale dynamic distributed environments, in particular peer-to-peer systems.
Peer-to-peer (P2P) systems are dynamic distributed systems in which nodes of equal roles and capabilities exchange information and services directly with each other. Due to its main design principle of being completely decentralized and self organizing—opposed to the Internet's “traditional” Client-Server paradigm—the P2P-concept emerges to a major design pattern for future applications, system components and infrastructural services, particularly with regard to reliability and resilience.
The Napster network is an example of P2P system, which emerged very fast as a content sharing infrastructure (mainly for MP3 music) among a geographically distributed user community. Other popular examples are Gnutella and Fast Track.
However, as P2P file sharing systems become increasingly popular, scalability and resilience have been recognized as the central challenge in designing such systems. For instance, Napster uses centralized directory service, which represents a single point of failure. Systems based on Gnutella use flooding to avoid the problem of Napster, but flooding is known to be highly bandwidth consuming. Furthermore deletion of a node or a group of nodes in a large P2P network may cause disconnection of a node or a subset of nodes from the network. Hence, maintaining the network always connected may imply an active or reactive exchanging of control information, which may also be bandwidth-consuming.
Therefore, FastTrack proposes an improvement to Gnutella's flooding, by introducing the notion of nodes differentiation. Resource query messages are not flooded to all the nodes in the network. FastTrack defines some nodes as “supernodes”, which are mostly fast computers with large computing resources, acting as temporally indexing server for other eventual slower nodes. Discovery messages are routed only through supernodes who are more susceptible to know the location of a requesting resource. FastTrack uses a kind of “structured” flooding, whereas it can not be guaranteed that a resource provider will be found even if available in the network; moreover, protocols such as FastTrack and Gnutella do not allow an uniform or consistent distribution of resources among nodes.
A series of P2P protocols such named Chord, Tapestry, Pastry, CAN, Viceroy, ODRI, CAN-D2B, distance halving, Broose, Koorde and Pagoda have been deployed recently in the research community, which are based on application layer overlay networking construction, to address the problem of routing and lookup efficiency as well as the resilience issue during network churns. The minimum value of the resource lookup distance in such networks generally varies between logd N and log N, N denoting the total number of nodes in a network, and d denoting the degree of a network, the degree being defined as the maximal number of outgoing links that is maintained by any node in the network.
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan: Chord: A scalable peer-to-peer lookup service for internet applications, SIGCOMM Comput. Commun. Rev., 31(4):149-160, 2001, describe a peer-to-peer network in which a key identifying a resource or desired data item is mapped onto a network node.
N. G. de Bruijn: A combinatorial problem, In Nederl. Akad. Wetensh. Proc. 49, pages 768-764, 1946, describes now called De Bruijn digraphs which are usually defined as directed graphs that are constructed on an alphabet. The vertices of the graphs are the words of this alphabet. A vertex is formed of D letters chosen from a set with cardinality d.
Per definition, a B (d, D) De Bruijn network forms a network of size N=dD. FIG. 10 illustrates an example of a B (2, 3) static the De Bruijn network with 8 nodes. Analysis of the De Bruijn graphs in the literature have shown interesting properties for their applications in static interconnected networks. Thereafter, each node in the network has exactly a constant number d of incoming and outgoing edges. That is, the routing table size of nodes in the network is constant. Moreover, there exists a path of length D=logd N hops between any two nodes in the network. Studies on the connectivity of the De Bruijn networks show that at most d−1 nodes can fail without disconnecting any node or any set of nodes from the network. Hence, the degree d is an important design parameter that can be varied to improve connectivity.
The lookup operation for a resource R in a De Bruijn network is equivalent to the routing operation from a node x to a node y=prefix (R), which eventually knows a provider of resource R. The pseudo-function prefix ( ) returns as result the k first elements right from R, with k≦D. Routing is achieved by a consecutive left shifting of x with R until a node y is reached. The left shifting operation on the node x results in a node y=kx+i mod N, i=topLetter (R, k), where topLetter (R, k) is a function that returns the kth letter from left of resource ID R and where k is the covered distance from the source. At any node x, a next-hop node y is chosen after left shifting of x so that y is a neighbor of x. Thus, routing in this way in the De Bruijn graph needs at most D hops from source to destination. For example, in FIG. 10 the message routing from 001 to 110 takes the path 001−>011−>111−>110 as depicted in FIG. 11.
There is a need to provide for an improved communication network and methods to route and locate information therein.